// 最大子数组和

package Leetcode;

import java.util.ArrayList;
import java.util.List;

class solution_053 {
    public int maxSubArray(int[] nums) {
        int max = nums[0];
        List<Integer> index = new ArrayList<>();
        for (int i = 0; i < nums.length; i++) {
            if (nums[i] > max)
                max = nums[i];
        }
        for (int i = 0; i < nums.length; i++) {
            if (nums[i] == max)
                index.add(i);
        }
        max = Integer.MIN_VALUE;
        for (int i : index) {
            max = Math.max(Greedy(i, nums), max);
        }
        return max;
    }

    public int Greedy(int index, int[] nums) {
        int left = index - 1;
        int right = index + 1;
        int max = nums[index];
        int currentValue = nums[index];
        while (right < nums.length || left >= 0) {
            int rightValue = right < nums.length ? nums[right] : Integer.MIN_VALUE;
            int leftValue = left >= 0 ? nums[left] : Integer.MIN_VALUE;
            int sign = 0;
            if (leftValue == rightValue) {
                int l = left - 1, r = right + 1;
                while (true) {
                    if (l < 0 & r >= nums.length) {
                        sign = 1;
                        break;
                    }
                    int rValue = r < nums.length ? nums[r] : Integer.MIN_VALUE;
                    int lValue = l >= 0 ? nums[l] : Integer.MIN_VALUE;
                    if (rValue > lValue) {
                        sign = 1;
                        break;
                    }
                    if (rValue < lValue) {
                        sign = -1;
                        break;
                    }
                    l--;
                    r++;
                }
            }
            if (leftValue > rightValue | (sign == -1)) {
                currentValue += leftValue;
                if (currentValue > max)
                    max = currentValue;
                left--;
            }
            if (leftValue < rightValue | sign == 1) {
                currentValue += rightValue;
                if (currentValue > max)
                    max = currentValue;
                right++;
            }
        }
        return max;
    }

    // public static void main(String[] args) {
    // int[] nums = new int[]{5,4,-1,7,8};
    // int index = 4;
    // System.out.println(Greedy(index, nums));
    // }
}


// 上述贪心算法错误

public class Solution053 {
    // 动态规划
    // dp[i]表示以nums[i]结尾的子数组的和的最大值
    public int maxSubArray(int[] nums) {
        int[] dp = new int[nums.length];
        dp[0] = nums[0];
        int max = nums[0];
        for (int i = 1; i < nums.length; i++) {
            if (dp[i - 1] > 0)
                dp[i] = dp[i - 1] + nums[i];
            else
                dp[i] = nums[i];
            max = Math.max(max, dp[i]);
        }
        return max;
    }
}
